#ifndef AI_SEARCH_H
#define AI_SEARCH_H



#include "ai.h"



//! @brief AI state, that is used to build a search tree
class ai_states_node
{

public:

	/**	@brief Constructor, that connects ai_game_state to states tree
	*	@param p parrent of the node
	*	@param s ai_game_state to be connected to the parent
	*/
	ai_states_node( ai_states_node* p, ai_game_state* s )
	{
		state = s;
		parent = p;
		if ( p != 0 )
		{
			p->children.push_back( this );
			depth = p->depth;
		}
		else
		//root node
		{
			depth = 1;
		}
	};

	//! @brief Destructor deletes all its children
	~ai_states_node();


	//! parent of this node
	ai_states_node* parent;
	//! list of children
	std::list< ai_states_node* > children;
	//! the ai_game_state
	ai_game_state* state;
	//! actual depth, where the node is
	unsigned int depth;
};



//! @brief The main algorithm class
class search_algorithm: public algorithm
{

public:

	//! @brief Constructor only assignes the name
	search_algorithm()
	{
		name = "Search algorithm";
	};

	/** @brief	Cloning function for init purposes
	*	@return	clone of the algorithm
	*/
	virtual algorithm* clone()
	{
		search_algorithm* cl = clonetpl< search_algorithm >();
		return cl;
	};

	//! @brief Function called at the beginning of every turn
	virtual void get_commands();


private:

	/**	@brief Expands given state and connects all children
	*	@param state_node node to expand, constraint: state_node != 0
	*/
	void search_state( ai_states_node* state_node );

	//! pointer to the root of the tree
	ai_states_node* search_tree;
	//! pointer to the best found state
	ai_states_node* best_state;

};



#endif